package com.tlvip.leetcode;

/**
 * <p>description：</p>
 * <p>copyright： copyright(C)2016-2099</p>
 * <p>Life is short,we need passion</p>
 * <p>Summary： </p>
 * <p>instructions： </p>
 * Date 2022/5/7</p>
 * Author mac
 *
 * @version 1.0
 */
public class ReverseList {

    public static void main(String[] args) {
        ListNode node4 = new ListNode(4, null);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);

        System.out.println(node1);
//        ListNode pre = revert(node1);
        ListNode pre = recursionList(node1);
        System.out.println(pre);
    }

    /**
     * 递归的方式解决反转链表问题
     * 图 算法-链表-反转-递归
     *
     * @param head 第一个节点
     * @return 最后一个节点
     */
    public static ListNode recursionList(ListNode head) {
        // 空链表无需反转
        if (head == null) {
            return head;
        }
        // 已经递归到末尾
        if (head.next == null) {
            return head;
        }
        // newHead指向不断改变，由第一个节点到最后一个节点，并保留最后一个节点位置
        ListNode newHead = recursionList(head.next);
        // 建立反向引用
        head.next.next = head;
        // 断开原先的正向引用
        head.next = null;
        return newHead;
    }


    /**
     * 迭代的方式解决反转链表问题
     * <p>
     * 图 算法-链表-反转-迭代
     *
     * @param head 第一个节点
     * @return 最后一个节点
     */
    public static ListNode revert(ListNode head) {
        ListNode pre = null, next;
        ListNode cur = head;
        // 遍历当前链表，直到末尾时，结束循环体
        // 对调当前节点和next节点的引用方向
        while (cur != null) {
            // 1. 找next节点
            next = cur.next;
            // 2. 反向cur.next指向，此时当前节点会与之前的next断链
            cur.next = pre;
            // 3. 移动pre指向当前节点，为下一次反向cur.next指向准备
            pre = cur;
            // 4. 移动当前节点指向next
            cur = next;
        }
        return pre;
    }

    static class ListNode {
        private int val;
        private ListNode next;

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
